package code1.graph;

import java.util.ArrayList;
import java.util.List;

public class P797 {


    boolean[] visited;

    List<List<Integer>> resList=new ArrayList<>();

    public void dfs(int cur,List<Integer> list,int[][] graph){
        if(cur==graph.length-1){
            resList.add(new ArrayList<>(list));         //注意这里不能直接添加list,不然全是同一个引用最后都是0
            return;
        }
        for(int i=0;i<graph[cur].length;i++){
            int next=graph[cur][i];
            if(!visited[next]){
                visited[next]=true;
                list.add(next);
                dfs(next,list,graph);
                list.remove(list.size()-1);
                visited[next]=false;
            }
        }

    }

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        visited=new boolean[graph.length];
        List<Integer> list=new ArrayList<>();
        visited[0]=true;
        list.add(0);
        dfs(0,list,graph);
        return resList;
    }


}
